package 不同路径II;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/4/29 12:59
 * @description:
 */
public class Solution2 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // dp空间优化

        int rowLen = obstacleGrid.length;
        int colLen = obstacleGrid[0].length;
        int[] dp = new int[colLen];
        // init dp
        for (int i = 0; i < colLen && obstacleGrid[0][i] == 0; i++) {
            // column
            dp[i] = 1;
        }
        System.out.println(Arrays.toString(dp));

        for (int i = 1; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                if (j != 0) {
                    dp[j] = obstacleGrid[i][j] == 1 ? 0 : dp[j - 1] + dp[j];
                } else if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                }
            }
            System.out.println(Arrays.toString(dp));
        }

        return dp[colLen - 1];
    }
}
